NAND memory integrated circuit chips are well known in the art. In a NAND memory chip, the memory is characterized by a number of blocks of storage, with each block containing a number of pages. A block is the minimum erasable unit. Thus, if a page in a block of NAND storage has already been written or programmed, it cannot be re-programmed or re-written again until the entire block with which the page is associated is erased. Therefore, in a block based flash file system (FFS), when replacing or overwriting a portion (such as a page) of a prewritten block, the overwrite data and the unchanged data portion of the block must be merged into a new erased block. Thus, as shown in FIG. 1, if pages 2 and 3 of the Original Block are to be over written, the new data for those pages are first saved in a Temporary Block, and then are merged with other pages of the Original Block into a Merged Block. Therefore, pages 0 and 1 are copied from the Original Block, pages 2 and 3 are copied from the Temporary Block, and the rest of the pages, from page 4 to end of the Original Block, are copied from the Original Block to the Merged Block. The Original and Temporary Blocks can then be erased for future use.
The merge operation can be very long when a block of NAND has 128 or 256 pages and moving each page may take multiple milliseconds. In addition, as the size of the blocks and programming time are increased, the merge time will increase.
Furthermore, in a NAND memory integrated chip, there are a large number of blocks, with only a few blocks allocated as Temporary Blocks. Referring to FIG. 2, there is shown a schematic level diagram of a NAND chip with one thousand (1,000) blocks of which nine hundred ninety two (992) blocks are allocated to storing data designated Data Blocks, while eight (8) blocks are allocated to Temporary Blocks. A typical write operation may be as follows. Let us assume that pages of data are to be written into Data Block 0, in locations where there is already pre-written data. Therefore, instead of performing the aforementioned merge operation, the new page(s) of data are first written into a Temporary Block, e.g. block 992, with block 992 assigned as being associated with Data Block 0.
If a page of new data is received by the NAND chip and it is destined for a page that is erased, anywhere in the Data Blocks 0-991, then the page of new data is written into that location. However, if the page of new data is destined for Data Block 0 where it is to write over another page of data, then it is stored in Temporary Block 992. Finally, if the page of new data is destined for a page, in a Data Block other than Data Block 0, e.g. Data Block 4, where it is to overwrite another page of data, then the page of new data is stored in Temporary Block 993, and Temporary. Block 993 is then associated with Data Block 4. Because the merge operation requires a long period of time, it is held off for as long as possible. This is done by storing the pages of new data in the Temporary Blocks. However, since in the prior art, very few Temporary Blocks are allocated (e.g. 8 blocks for every 1,000 blocks of data), because of the desire to use as many blocks for data as possible, the NAND memory chip will quickly run out of Temporary Blocks. For example, in the above example, if a ninth “write” operation is received for a page of new data which is to overwrite a ninth different Data Block, then a merge operation must first be performed to free up a temporary block. As NAND chips increase in storage capacity and the number of blocks increases, the likelihood of the NAND chip quickly requiring a merge operation to free up a temporary block increases.
One prior art solution to the problem of more closely resembling a true random write operation with the NAND chip having few merge operations before the page(s) of new data can be written was to have as many temporary blocks as data blocks. With a 1:1 ratio of temporary block to data block, the requirement for merge operation dramatically decreases. This solution however, results in far fewer data blocks available for storage of user data. Hence a new solution is desired.